<?php
/*
993. 二叉树的堂兄弟节点
在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。



示例 1：
            1
           / \
          2   3
         /
        4
输入：root = [1,2,3,4], x = 4, y = 3
输出：false


示例 2：
            1
           / \
          2   3
           \   \
            4   5

输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true


示例 3：
            1
           / \
          2   3
           \
            4
输入：root = [1,2,3,null,4], x = 2, y = 3
输出：false


提示：

二叉树的节点数介于 2 到 100 之间。
每个节点的值都是唯一的、范围为 1 到 100 的整数。

https://leetcode.cn/problems/cousins-in-binary-tree/


*/

require_once '../class/TreeNode.class.php';

$arr = [1,2,3,null,4,null,5];
$x = 5;
$y = 4;
$root = generateTreeByArray($arr);

var_dump((new Solution993())->isCousins($root, $x, $y));


class Solution993
{

    protected $x = ['parent' => null, 'depth' => null];
    protected $y = ['parent' => null, 'depth' => null];


    function isCousins($root, $x, $y) {
        $this->dfs($root, null, $x, $y, 0);
        return $this->x['parent'] != $this->y['parent'] && $this->x['depth'] == $this->y['depth'];
    }

    function dfs($root, $parent, $x, $y, $depth)
    {
        if ($root == null) {
            return;
        }
        if ($root->val == $x) {
            $this->x['parent'] = $parent->val;
            $this->x['depth'] = $depth;
        }
        if ($root->val == $y) {
            $this->y['parent'] = $parent->val;
            $this->y['depth'] = $depth;
        }
        $this->dfs($root->left, $root, $x, $y, $depth + 1);
        $this->dfs($root->right, $root, $x, $y, $depth + 1);

    }

    function bfs($root)
    {
        $queue = new SplQueue();
        $queue->enqueue(['node' => $root, 'parent' => null]);
        $level = 0;
        while (!$queue->isEmpty()) {
            $count = $queue->count();
            for ($i = 0; $i < $count; $i++) {
                $cur = $queue->dequeue();
                $node = $cur['node'];

                $this->arr[$level][] = $cur->val;
                if ($cur->left) {
                    $queue->enqueue(['node' => $cur->left, 'parent' => $node->val]);
                }
                if ($cur->right) {
                    $queue->enqueue(['node' => $cur->right, 'parent' => $node->val]);
                }
            }
            $level++;
        }
    }


}


